#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+10;
int f[20][N];
int g[20][N];
int a[N];
int lg[N];
int n;
int st[N];
void init(int n)
{
	for(int i=0;i<=19;i++)
	{
		for(int j=1;j+(1<<i)-1<=n;j++)
		{
			if(!i)
			{
				f[i][j]=a[j];
				g[i][j]=a[j];
			} 
			else
			{
				f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
				g[i][j]=min(g[i-1][j],g[i-1][j+(1<<i-1)]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		lg[i]=__lg(i);
	}
}

int query_max(int l,int r)
{
	int k=lg[r-l+1];
	
	return max(f[k][l],f[k][r-(1<<k)+1]);
}

int query_min(int l,int r)
{
	int k=lg[r-l+1];
	
	return min(g[k][l],g[k][r-(1<<k)+1]);
}

int check(int x)
{
	for(int i=1;i+x<=n;i+=x)
	{
		int l=i;
		int r=i+x-1;
		int mmax=query_max(l,r);
		l=i+x;
		r=min(n,i+x+x-1);
		int mmin=query_min(l,r);
		if(mmin<mmax) return 0;
	}
	return 1;
}

int main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	init(n);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(st[i])
		{
			cnt++;
			continue;
		}
		if(check(i))
		{
			cnt++;
			for(int j=1;j*i<=n;j++)
			{
				st[j]=1;
			}
		}
	}
	
	cout<<cnt;

	return 0;
}

